/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: Lenovo
 * Date: 2025-07-24
 * Time: 23:07
 */
public class Sort {
    public Sort(){
    }

    int end;
    public int[] smallestK(int[] arr, int k) {
        int[] brr=new int[k];
        if(k==0){
            return brr;
        }
        end=arr.length;
        sort(arr);
        for(int i=0;i<brr.length;i++){
            brr[i]=pop(arr);
        }
        return brr;
    }
    public void sort(int[] arr){
        int root=(arr.length-1-1)/2;
        while(root>=0){
            down(arr,root);
            root--;
        }
    }
    public void down(int[] arr,int i){
        int root=i;
        int s=root*2+1;
        while(s<end){
            if(s+1<end&&arr[s+1]<arr[s]){
                s++;
            }
            if(arr[s]<arr[root]){
                fun(arr,s,root);
            }
            else{
                break;
            }
            root=s;
            s=root*2+1;
        }
    }
    public int pop(int[] arr){
        int n=arr[0];
        fun(arr,0,end-1);
        end--;
        down(arr,0);
        return n;
    }
    public void fun(int[] arr,int i,int j){
        int n=arr[i];
        arr[i]=arr[j];
        arr[j]=n;
    }
}
